버블 정렬 (Bubble sort)

시간 복잡도(Time complexity): O(n^2)

가장 간단한 정렬 알고리즘이지만 시간 복잡도(Time complexity)가 높기 때문에 거의 사용되지 않는다.

인접한 요소를 비교하여 순서대로 되어 있지 않으면 둘의 위치를 바꿈(swap)으로써 정렬한다.

ref: https://commons.wikimedia.org/wiki/File:Bubble-sort-example-300px.gif

우선, 최적화 되지 않은 버블 정렬 코드를 먼저 살펴보자.

// This implementation is not optimized.
function bubbleSort(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (j == 0) {
        console.log(`${i + 1} traverse started!`);
      }
      if (arr[j] > arr[j + 1]) {
          // swap arr[j] and arr[j+1]
          console.log('swapped', arr[j], arr[j + 1]); 
          let tmp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = tmp;
      } else {
        console.log('unswapped', arr[j], arr[j + 1]); 
      }
      count++;
    }
  }
  console.log('unoptimized', arr, `finished in ${count}`); 
}

var arr = [234, 43, 55, 63, 5, 6, 235, 547]; 

bubbleSort(arr); 

// Log for unoptimized bubble sort
1 traverse started!
swapped 0 234 43
swapped 1 234 55
swapped 2 234 63
swapped 3 234 5
swapped 4 234 6
unswapped 5 234 235
unswapped 6 235 547

2 traverse started!
unswapped 0 43 55
unswapped 1 55 63
swapped 2 63 5
swapped 3 63 6
unswapped 4 63 234
unswapped 5 234 235

3 traverse started!
unswapped 0 43 55
swapped 1 55 5
swapped 2 55 6
unswapped 3 55 63
unswapped 4 63 234

4 traverse started!
swapped 0 43 5
swapped 1 43 6
unswapped 2 43 55
unswapped 3 55 63

5 traverse started!
unswapped 0 5 6
unswapped 1 6 43
unswapped 2 43 55

6 traverse started!
unswapped 0 5 6
unswapped 1 6 43

7 traverse started!
unswapped 0 5 6
unoptimized [
   5,   6,  43,  55,
  63, 234, 235, 547
] finished in 28

이번엔 최적화된 버블 정렬 코드이다.

// Optimized implementation
function optimizedBubbleSort(arr) {
  let count = 0;
  // let swapped = false;
  for (let i = 0; i < arr.length; i++) {
    let swapped = false;
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (j == 0) {
        console.log(`${i + 1} traverse started!`);
      }
      if (arr[j] > arr[j + 1]) {
          console.log('swapped', j, arr[j], arr[j + 1]); 
          // swap arr[j] and arr[j+1]
          let tmp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = tmp;
          swapped = true;
      } else {
        console.log('unswapped', j, arr[j], arr[j + 1]); 
      }
      count++;
    }
    if (swapped == false) {
      break;
    }
  }
  console.log('optimized', arr, `finished in ${count} times`); 
}

var arr = [234, 43, 55, 63, 5, 6, 235, 547]; 

bubbleSort(arr);

// Log for an optimized solution.
1 traverse started!
swapped 0 234 43
swapped 1 234 55
swapped 2 234 63
swapped 3 234 5
swapped 4 234 6
unswapped 5 234 235
unswapped 6 235 547

2 traverse started!
unswapped 0 43 55
unswapped 1 55 63
swapped 2 63 5
swapped 3 63 6
unswapped 4 63 234
unswapped 5 234 235

3 traverse started!
unswapped 0 43 55
swapped 1 55 5
swapped 2 55 6
unswapped 3 55 63
unswapped 4 63 234

4 traverse started!
swapped 0 43 5
swapped 1 43 6
unswapped 2 43 55
unswapped 3 55 63

5 traverse started!
unswapped 0 5 6
unswapped 1 6 43
unswapped 2 43 55

 optimized [
   5,   6,  43,  55,
  63, 234, 235, 547
] finished in 25